package com.example.datastructure.find;

/**
 * 二分法查找
 */
public class HalfSort {

    /**
     * 传入数组和要查找的值，数组必须有序
     *
     * @param array
     * @param key
     * @return
     */
    public static int halfSort(int[] array, int key) {
        int start = 0;                   //数组开始位置下标
        int end = array.length - 1;     //数组结束位置下标
        int index = -1;                 //是否有key值得数组下标
        while (start <= end) {          //判断是否可以继续二分
            int half = (start + end) / 2;  //找数组中间数值
            if (array[half] == key) {
                index = half;
                break;
            } else if (array[half] > key) {   //如果array[half] > key ,说明key在左边，将数组结束位置下标更新为当前中间值的左边一位
                end = half - 1;
            } else {
                start = half + 1;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int[] number = {1, 2, 3, 4, 5, 6, 7, 8, 9,10};
        int key = 1;
        int result = HalfSort.halfSort(number, key);
        if (result == -1) {
            System.out.println("当前数据不存在");
        } else {
            System.out.println(result);
        }
    }
}
